class Solution {
public:
    vector<int> father,rank;
    int find(int u){
        return u == father[u] ? u : find(father[u]);
    }
    void Union(int u,int v){
        int x = find(u);
        int y = find(v);
        if(x == y) return;
        
        if(rank[x] < rank[y]){
            swap(x,y);
        }
        
        rank[x] += rank[y];
        father[y] = x;
    }
    
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        father.resize(n);
        rank.resize(n,1);
        
        for(int i = 0;i < n;i++){
            father[i] = i;
        }
        
        for(auto& vc : pairs){
            Union(vc[0],vc[1]);
        }
        
        unordered_map<int,vector<int> > ump;
        for(int i = 0;i < n;i++){
            int x = find(i);
            ump[x].push_back(s[i]);
        }
        
        
        for (auto& [x, vec] : ump) {
            sort(vec.begin(), vec.end(), greater<int>());
        }

        
        for(int i = 0;i < n;i++){
            int j = find(i);
            s[i] = ump[j].back();
            ump[j].pop_back();
        }
        
        return s;
    }
};
